/**
 * @author 雷明浩
 * @date 2025/7/3 10:56
 */
public class Solve {
    // 岛屿数量
    // https://www.nowcoder.com/practice/0c9664d1554e466aa107d899418e814e?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    private boolean[][] vis;
    private final int[] x = {-1,0,0,1};
    private final int[] y = {0,-1,1,0};
    public int solve (char[][] grid) {
        // write code here
        int ret = 0;
        int rowLen = grid.length;
        int colLen = grid[0].length;
        vis = new boolean[rowLen][colLen];
        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < colLen; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    ret++;
                }
            }
        }
        return ret;
    }

    private void dfs(char[][] grid, int row, int col) {
        for (int k = 0; k < 4; k++) {
            int i = row + x[k];
            int j = col + y[k];
            if (i >= 0 && i < grid.length
                    && j >= 0 && j < grid[0].length
                    && !vis[i][j] && grid[i][j] == '1') {
                vis[i][j] = true;
                grid[i][j] = '0';
                dfs(grid, i, j);
            }
        }
    }
}